Sebelum 1760, Dato' Undang Luak Sungei Ujong menggunakan gelaran Dato' Penghulu Menteri, iaitu gelaran yang diwarisi sejak kedatangan Parameswara ke Sungei Ujong sebelum pengasasan Kesultanan Melayu Melaka.

Mengikut Sejarah Melayu, ketika Sultan Muzaffar Shah memerintah Melaka (1445-1458) Sungei Ujong adalah di bawah pegangan Bendahara Paduka Raja Tun Perak dan Seri Nara Diraja Tun Ali. Ketika pemerintahan Sultan Mansur Shah (1456-1477), Dato Penghulu Menteri di Sungai Ujong dicatatkan bernama Tun Tuakal.

Bagaimanapun, Tun Tuakal dihukum bunuh oleh Sultan Mansur Shah dan sejak itu Sungei Ujong diperintah oleh Seri Nara Diraja Tun Ali dan keturunan beliau sehingga hari ini.

Riwayat Sungei Ujong dan catatan Belanda merekodkan pada sekitar 1640-an, Bendahara Kesultanan Johor Lama, Tun Jenal yang bergelar Bendahara Skudai (keturunan Seri Nara Diraja Tun Ali) menetap di Sungei Ujong dan berkahwin dengan ketua tempatan, iaitu seorang wanita dikenali Batin Sibu Jaya.

Perkahwinan itu melahirkan Dato Kelambu (Muhammad Tumbu) , To' Musang, Dato' Semerga dan To' Seri Mani. Dato Kelambu dan To' Musang mewarisi pemerintahan Sungei Ujong daripada Tun Jenal selaku Dato Penghulu Menteri Sungei Ujong dan berkuasa di darat.

Manakala Dato Semerga mewarisi pegangan Tun Jenal yang meliputi laluan air (sungai) dan kawasan pantai di Luak Sungei Ujong. Keturunan Dato Semerga kemudian diiktiraf oleh Sultan Johor sebagai Dato' Shahbandar Sungei Ujong sejak 1715.

Keturunan Dato Kelambu (Muhammad Tumbu) dan To' Musang dikenali sebagai Waris Klana dan kekal memerintah Luak Sungei Ujong sebagai Dato Penghulu Menteri sehingga 1760, apabila Dato Bador mula menggunakan gelaran Dato' Klana Petra selepas memperoleh cop mohor kebesaran dan perakuan kedaulatan sebagai pemerintah Luak Sungei Ujong daripada Sultan Johor.